#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2020/10/01
# @Author   :Changshu
# @File     :practice_204.py
# 统计所有小于非负整数 n 的质数的数量。
'''这题搜到一个非常牛逼的算法,叫做厄拉多塞筛法. 比如说求20以内质数的个数,
	首先0,1不是质数.2是第一个质数,然后把20以内所有2的倍数划去.2后面紧跟的数即为下一个质数3,
	然后把3所有的倍数划去.3后面紧跟的数即为下一个质数5,再把5所有的倍数划去.以此类推.
'''
''''''
# from math import sqrt
def countPrimes(n:int)->int:
	if n<3:
		return 0
	# 假设所有的数都是质数
	output=[1]*n
	# 0和1不是质数，2是质数
	output[0],output[1]=0,0
	for i in range(2,int(n**0.5)+1):
		if output[i]==1:
			output[i*i:n:i]=[0]*len(output[i*i:n:i])
	return sum(output)


if __name__ == '__main__':
	n=100
	print(countPrimes(n))